#include <iostream>
using namespace std;

typedef struct BiTreeNode {
    int data;
    struct BiTreeNode *leftNode,*rigthNode;
}BiTreeNode;

typedef struct BiTreeNode *BiTree;

void InitBiTree(BiTree *biTree,int data) {
    (*biTree) = (BiTree)malloc(sizeof(BiTreeNode));
    (*biTree)->leftNode = NULL;
    (*biTree)->rigthNode = NULL;
    (*biTree)->data = data;
}

bool AddDataToBiTree(BiTree *biTree,int data) {
    BiTree tempNode = (*biTree);
    while (tempNode) {
        if (tempNode->data > data) {
            if (tempNode->leftNode == NULL) {
                BiTree newNode = (BiTree)malloc(sizeof(BiTreeNode));
                newNode->data = data;
                tempNode->leftNode = newNode;
                break;
            } else {
                tempNode = tempNode->leftNode;
            }
        } else if (tempNode->data < data) {
            if (tempNode->rigthNode == NULL) {
                BiTree newNode = (BiTree)malloc(sizeof(BiTreeNode));
                newNode->data = data;
                tempNode->rigthNode = newNode;
                break;
            } else {
                tempNode = tempNode->rigthNode;
            }
        } else {
            return false;
        }
    }
    return true;
}

void PrintBiTree(BiTree biTree) {
    if (biTree != NULL) {
        PrintBiTree(biTree->leftNode);
        printf("%d",biTree->data);
        PrintBiTree(biTree->rigthNode);
    }
}

void SearchBiTree(BiTree biTree,int data) {
    if (biTree != NULL) {
        if (biTree->data == data) {
            printf("找到%d\n",data);
            return;
        }
        printf("继续查找%d\n",data);
        SearchBiTree(biTree->leftNode,data);
        SearchBiTree(biTree->rigthNode,data);
    }
}

void FindMax(BiTree biTree) {
    if (biTree->rigthNode == NULL) {
        printf("最大值是%d\n",biTree->data);
        return;
    }
    FindMax(biTree->rigthNode);
}

void FindMin(BiTree biTree) {
    if (biTree->leftNode == NULL) {
        printf("最小值是%d\n",biTree->data);
        return;
    }
    FindMin(biTree->leftNode);
}

int main(){
    BiTree biTree;
    InitBiTree(&biTree,6);
    AddDataToBiTree(&biTree,1);
    AddDataToBiTree(&biTree,8);
    AddDataToBiTree(&biTree,4);
    AddDataToBiTree(&biTree,9);
    AddDataToBiTree(&biTree,2);
    PrintBiTree(biTree);
    SearchBiTree(biTree,9);
    FindMin(biTree);
    FindMax(biTree);
}
